/* 
 * Copyright (c) 2004-2005 Massachusetts Institute of Technology. This code was
 * developed as part of the Haystack (http://haystack.lcs.mit.edu/) research 
 * project at MIT. Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation files (the 
 * "Software"), to deal in the Software without restriction, including without 
 * limitation the rights to use, copy, modify, merge, publish, distribute, 
 * sublicense, and/or sell copies of the Software, and to permit persons to whom
 * the Software is furnished to do so, subject to the following conditions: 
 * 
 * The above copyright notice and this permission notice shall be included in 
 * all copies or substantial portions of the Software. 
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER  
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE. 
 */
/*
 * Created on Sep 6, 2004
 *
 */
package jiggle.relo;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import jiggle.Cell;
import jiggle.Graph;
import jiggle.Vertex;

import org.eclipse.draw2d.geometry.Insets;
import org.eclipse.draw2d.geometry.Rectangle;

/**
 * @author vineet
 *  
 */
public class Subgraph extends Graph {

    public Insets subgraphBorder = new Insets(10);

    /**
     * @param g
     */
    public Subgraph(Graph g) {
        setContext(g);
        centralDistances = g.centralDistances;
    }

	//public double getWeight () {return super.getWeight() * numberOfVertices;}
	//public void setWeight (double w) {super.setWeight(w/numberOfVertices);}
    
    private void getMinMaxCoords(double[] minCoord, double[] maxCoord) {
        int nd = getDimensions();
        int sgnv = getNumberOfVertices();
        
        if (sgnv == 0) {
            for (int j = 0; j < nd; j++) {
                minCoord[j] = 0;
                maxCoord[j] = 0;
            }
            return;
        }
        
        double[] vertexCoords = getBorderCoords(vertices.get(0));
        double[] vertexSize = getBorderSize(vertices.get(0));
        
        for (int j = 0; j < nd; j++) {
            minCoord[j] = vertexCoords[j] - (vertexSize[j] / 2);
            maxCoord[j] = vertexCoords[j] + (vertexSize[j] / 2);
        }

        for (int sv = 0; sv < sgnv; sv++) {
            vertexCoords = getBorderCoords(vertices.get(sv));
            vertexSize = getBorderSize(vertices.get(sv));
            for (int j = 0; j < nd; j++) {
                minCoord[j] = Math.min(minCoord[j], vertexCoords[j] - (vertexSize[j] / 2));
                maxCoord[j] = Math.max(maxCoord[j], vertexCoords[j] + (vertexSize[j] / 2));
            }
        }
    }
    
    public double[] getBorderSize() {
        int nd = getDimensions();

        double minCoord[] = new double[nd];
        double maxCoord[] = new double[nd];

        getMinMaxCoords(minCoord, maxCoord);

        double retSize[] = new double[nd];
        for (int j = 0; j < nd; j++) {
            int border;
            if (j==0) {
                border = subgraphBorder.getWidth();
            } else if (j==1) {
                border = subgraphBorder.getHeight();
            } else {
                border = (subgraphBorder.getHeight() + subgraphBorder.getWidth())/2;
            }
            retSize[j] = border + maxCoord[j] - minCoord[j];
        }
        return retSize;
    }

    public void dmpInfo() {
        int nd = getDimensions();

        double minCoord[] = new double[nd];
        double maxCoord[] = new double[nd];

        getMinMaxCoords(minCoord, maxCoord);

        double retSize[] = new double[nd];
        for (int j = 0; j < nd; j++) {
            retSize[j] = maxCoord[j] - minCoord[j];
        }
        
        System.err.println("Dumping...");
        System.err.println("Min: " + minCoord[0] + "," + minCoord[1]);
        System.err.println("Max: " + maxCoord[0] + "," + maxCoord[1]);
        System.err.println("Sz : " + retSize[0] + "," + retSize[1]);
        if (Double.isNaN(minCoord[0])) {
            System.err.println("V0C: " + vertices.get(0).getCoords()[0] + "," + vertices.get(0).getCoords()[1]);
            System.err.println("V0S: " + vertices.get(0).getSize()[0] + "," + vertices.get(0).getSize()[1]);
        } else {
        }
    }

    @SuppressWarnings("unused")
	private void dmp(double[] d) {
        for (int i = 0; i < d.length; i++) {
            System.err.print(d[i] + " ");
        }
        System.err.println();
    }

    public double[] getBorderCoords() {
        int nd = getDimensions();

        double minCoord[] = new double[nd];
        double maxCoord[] = new double[nd];

        getMinMaxCoords(minCoord, maxCoord);

        double retCoords[] = new double[nd];
        for (int j = 0; j < nd; j++) {
            retCoords[j] = (maxCoord[j] + minCoord[j])/2;
        }
        return retCoords;
    }
    
    // border family reaches in and gets the real size/coords
    private double[] getBorderCoords(Cell v) {
        if (v instanceof Subgraph) {
            return ((Subgraph)v).getBorderCoords();
        } else {
            return v.getCoords();
        }
    }
    private double[] getBorderSize(Cell v) {
        if (v instanceof Subgraph) {
            return ((Subgraph)v).getBorderSize();
        } else {
            return v.getSize();
        }
    }

    @Override
    public Rectangle getBounds() {
        int nd = getDimensions();

        double minCoord[] = new double[nd];
        double maxCoord[] = new double[nd];

        getMinMaxCoords(minCoord, maxCoord);
        
        Rectangle containedRect = new Rectangle((int) minCoord[0], (int) minCoord[1],
                (int) (maxCoord[0] - minCoord[0]), 
                (int) (maxCoord[1] - minCoord[1]));
        return containedRect.expand(subgraphBorder);
    }

	@Override
    public void recomputeBoundaries () {
	    //(new RuntimeException("tst")).printStackTrace();
	    int dimensions = getDimensions();
		double[] coords = getCoords();
        double[] size = getSize();
        double[] min = getMin();
        double[] max = getMax();
        // access private members
        // basically Cell.recomputeBoundaries
		for (int i = 0; i < dimensions; i++) {
            min [i] = coords [i] - size [i] / 2;
			max [i] = coords [i] + size [i] / 2;
		}
	}
	
	public void getChildrenRecursively(Set<Cell> s) {
        for (int i = 0; i < vertices.size(); i++) {
            Cell v = vertices.get(i);
            if (v instanceof Subgraph)
                ((Subgraph)v).getChildrenRecursively(s);
            else
                s.add(v);
        }
	    
	}
	
	public Map<Vertex,Set<Vertex>> mapCellsToCC = null;
	public Set[] arrCC = null;
	public int largestCC = -1;
	
	public void initConnectedMap() {
		mapCellsToCC = new HashMap<Vertex,Set<Vertex>>();

		//Set children = new HashSet(Arrays.asList(vertices));
        for (int i = 0; i < vertices.size(); i++) {
            Cell c = vertices.get(i);
            if (!(c instanceof Vertex)) continue;
            
            // already has a component attached to it
            if (mapCellsToCC.containsKey(c)) continue;
            
            Vertex v = (Vertex) c;

            Set<Vertex> connectedComponent = new HashSet<Vertex>();
            connectedComponent.add(v);
            mapCellsToCC.put(v, connectedComponent);
            
            Iterator neighbors = v.getAllNeighbors().iterator();
            while (neighbors.hasNext()) {
                Vertex neighbor = (Vertex) neighbors.next();
                if (mapCellsToCC.containsKey(neighbor)) {
                    connectedComponent = mergeComponents( mapCellsToCC.get(neighbor), connectedComponent);
                }
            }
            
        }
        
        Set<Set<Vertex>> setCC = new HashSet<Set<Vertex>> (mapCellsToCC.values());
        arrCC = (Set[]) setCC.toArray(new Set[] {});
        
        largestCC = 0;
        for (int i=1; i<arrCC.length; i++) {
            if (arrCC[largestCC].size() < arrCC[i].size()) {
                largestCC = i;
            }
        }
	}

    private Set<Vertex> mergeComponents(Set<Vertex> connectedComponent1, Set<Vertex> connectedComponent2) {
        // do connectedComponent2 => connectedComponent1
        
        // remap
        Iterator connectedComponent2It = connectedComponent2.iterator();
        while (connectedComponent2It.hasNext()) {
            Vertex cc2Vertex = (Vertex) connectedComponent2It.next();
            mapCellsToCC.put(cc2Vertex, connectedComponent1);
        }
        
        // add
        connectedComponent1.addAll(connectedComponent2);
        return connectedComponent1;
    }

}